package com.atues.arrays.jieyvshui42;

class Solution {
    public int trap(int[] height) {
        //遍历数组，设置一个开头和一个结尾的指针，分别为0和1
        //首先要知道雨水如何算，这里一种算的方法就是对于每个坐标i，他所能界的雨水就是左右两边最大长度，leftMax和rightMax的最小值-height【i】，有这个思想那就很好做了
        //1.dp算法，维护两个数组leftMax[]和rightMax【】，表示i左边和右边的最大高度，包括i本身，
            //初始化dp
        int n = height.length;
        int leftMax[] = new int[height.length], rightMax[] = new int[height.length];
        leftMax[0] = height[0];
        rightMax[n - 1] = height[n - 1];
        //状态转移方程 leftMax[i+1] = max(leftMax[i],height[i+1],rightMax类似
        for (int i = 0; i < n - 1; i++) {
            leftMax[i + 1] = Math.max(leftMax[i], height[i + 1]);
        }
        for (int j = n - 1; j > 0; j--) {
            rightMax[j - 1] = Math.max(rightMax[j],height[j-1]);
        }
        int res = 0;
        //收集结果
        for (int i = 0; i < n; i++) {
            res += Math.min(rightMax[i], leftMax[i]) - height[i];
        }
        return res;
    }
    //借鉴背包优化dp算法思想，该dp可以进行压缩，将以为素组压缩为一个数
    //
    public int trap1(int[] height) {

        //因为dp数组是分别往左和往右遍历然后再找到leffMax和rightMax，如果把他作为单个数，分别定义左右两个指针，i，j，那么同时两个指针往内边例
        //直至j>i就结束
        //因为分别同时左右遍历所以就能同时更新leftMax和rightMax
        //最关键的是计算逻辑
        //首先这样遍历肯定是要同时计算i，j所能接的雨水，同时更新rM和lM

        //初始化dp
        int n = height.length;
        int leftMax = height[0], rightMax = height[n -1];
        int i=0,j = n -1;
        //状态转移方程 leftMax[i+1] = max(leftMax[i],height[i+1],rightMax类似

        int res = 0;
        //收集结果
        while (i <= j) {
            leftMax = Math.max(leftMax, height[i]);
            rightMax = Math.max(rightMax, height[j]);
            //收集结果
//            if (leftMax <  rightMax) {//则必有leftMax < rightMax,则做指针的右边一定有大于做指针左边所有板子的高度，那么短板原理，
//                res += leftMax - height[i];
//                i++;
//            }else{
//                res += rightMax - height[j];
//                j--;
//            }

            if (height[i] < height[j]) {//那么那么至少rightMax[i]是大于height[i]，那么短板一定存在（我指的是最大左右两边的短板）一定在左边；
                res += leftMax - height[i];
                ++i;
            } else {
                res += rightMax - height[j];
                --j;
            }

        }

        return res;
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(solution.trap1(height));
    }
}